# L931：下降路径最小和
MAX_UINT = 65536


# dp函数自顶而下的求解
# def minFallingPathSum(matrix):
#     m = len(matrix)
#     n = len(matrix[0])
#
#     memo = [[10000 for j in range(n)] for i in range(m)]
#     def dp(i, j):
#         if i < 0 or j < 0 or j >= n:
#             return MAX_UINT
#
#         # base case
#         if i == 0:
#             return matrix[0][j]
#         # 查找备忘录
#         if memo[i][j] != 10000:
#             return memo[i][j]
#
#         # 递归 状态转移
#         memo[i][j] = min(dp(i-1, j-1), dp(i-1, j), dp(i-1, j+1)) + matrix[i][j]
#
#         return memo[i][j]
#
#     res = MAX_UINT
#     for i in range(n):
#         res = min(dp(m-1, i), res)  # 终点
#     return res

# 自第而上的求解
def minFallingPathSum(matrix):
    m = len(matrix)
    n = len(matrix[0])

    dp = [[MAX_UINT for j in range(n)] for i in range(m)]  # 从第一行的某个位置走到当前的(i, j)位置所需要的最短路径和为dp[i][j]

    # base case
    for i in range(n):
        dp[0][i] = matrix[0][i]  # 第0行所有元素即为matrix对应的值

    for i in range(1, m):
        for j in range(0, n):
            if j < 0 or j >= n-1:
                continue
            dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + matrix[i][j]

    res = MAX_UINT
    for i in range(n):
        res = min(res, dp[m-1][i])
    return res

grid = [[1, 2, 3], [1, 4, 0], [2, 1, 1]]
print("{}的最小下降距离 {}".format(grid, minFallingPathSum(grid)))


# L64 最小路径和 从左上角走到右下角
# dp数组自底而上
def minPathSum(grid):
    m = len(grid)
    n = len(grid[0])

    dp = [[MAX_UINT for _ in range(n)] for _ in range(m)]  # 从左上角grid(0,0)走到(i,j)的最小路径和为dp(i,j)

    # base case
    dp[0][0] = grid[0][0]
    # 从(0,0)走到第0行的任意位置
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    # 从(0,0)走到第0列的任意位置
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]

    # 状态转移 dp[i][j] = min(dp[i-1][j]) + grid[i][j-1]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i][j]

    return dp[m-1][n-1]

grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
print("{}的最小下降距离 {}".format(grid, minPathSum(grid)))

